package 题目集.动态规划.最长递增子序列;

import java.util.*;

/**
 * https://www.luogu.com.cn/problem/P8736
 */
public class 最长上升子序列_L星球 {
    /**
     * 找出数量最多的升序数列
     * 思路:dp[i]：以i结尾s[0...i]中最大的数量
     * 1.s[i]>s[dp[i-1]]，大于之前的最大值dp[i]=dp[i-1]+1
     * 2.dp[i]=1    //要自己
     */
    static int maxN = 1000001;
    static char[] path = new char[maxN];
    static List<String> names = new ArrayList<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String lineA = sc.nextLine();
        int length = lineA.length();
        for (int i = 0; i < length; i++) {
            int s = 0;
            char c;
            do {
                c = lineA.charAt(i++);
                path[s++] = c;
            } while (i < length && ((c = lineA.charAt(i)) < 'A' || c > 'Z'));
            i--;
            names.add(new String(path, 0, s));
        }
        n = names.size();
        List<String> strings = fun();
        strings.forEach(System.out::print);

    }

    static String[] ends;   //记录当前最长子序列长度下，递增最慢的子序列。
    static Map<String, String> map = new HashMap<>();  //记录当前字符的上一个比自己小的字符
    static int n;

    /**
     * 解法2：贪心+二分
     * 如果我们要使上升子序列尽可能的长，则我们需要让序列上升得尽可能慢，因此我们希望每次在上升子序列最后加上的那个数尽可能的小。
     * 在方法1中，dp[i]依赖的，是一个比自己小的上升最慢的子序列结尾。
     * 我们维护一个数组 d[i]，d[i]表示长度为 i 的最长上升子序列的末尾元素的最小值。
     * 上面两句有些不好理解，简单讲的话。
     *      就是dp[i]之前的最长递增子序列长度为len，我们维护一个数组，这个数组保存着i位置之前的，len个递增的序列。
     *      因为要让上升满足尽可能小，所以找到之前第一个比自己大的位置，然后替换掉，方便后面的位置插入。而自己的长度就是这个位置+1。
     *      而查找比自己大的过程，可以用二分加速
     */
    public static List<String> fun() {
        ends = new String[n];
        int len = 1;    //记录当前最长子序列长度
        ends[0] = names.get(0);
        for (int i = 1; i < n; i++) {
            String cur = names.get(i);
            int index = find(cur, 0, len);
            map.put(cur, map.get(ends[index]));
            if (index == len) {
                map.put(cur, ends[index - 1]);
                len++;
            }
            ends[index] = cur;  //替换掉比自己大的位置
        }
        LinkedList<String> res = new LinkedList<>();
        String last = ends[len - 1];
        while (last != null) {
            res.addFirst(last);
            last = map.get(last);
        }
        return res;
    }

    //找到第一个比n大的位置，如果没有，返回末尾的下一个位置
    public static int find(String s, int l, int r) {
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (compare(s,ends[mid])) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        return l;
    }
    public static boolean compare(String a, String b) {
        return a.compareTo(b) > 0;
    }
    public static boolean compare(int i, int j) {
        return names.get(i).compareTo(names.get(j)) > 0;
    }
}
